/* File: maze_4c.c
 * --------------------
 * Author: Albin Olausson & Stella Wallin
 * Last modified: 2014-04-22
  *Task: This program solves a maze by recursive backtracking 
 * and prints the x and y coordinates that make out the
 * solution.
 */

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/* Private function prototypes */

static bool FindPath(pointT pt, pointT *path);
static pointT AdjacentPoint(pointT pt, directionT dir);

/* Prototypes */

void addSquareToArray(pointT pt, pointT *path);
void InitArray(pointT *path);

/* Constants */

#define MaxPath 100

/* Main program */

main()
{	
	string MazeFile;
	int i = 0, j;
	pointT *path;

	printf("Program by S. Wallin & A. Olausson.\n\n");
	path = NewArray(MaxPath, pointT);
	InitArray(path);
	printf("Input name of maze file: \n");
	MazeFile = GetLine();
    InitGraphics();
    ReadMazeMap(MazeFile);

	if (FindPath(GetStartPosition(), path)){
		while(path[i].x >= 0){
		i++;
		}
		printf("The following path is a solution:\n");
		for(j = i-1; j>= 0; j--)
			printf("(%d, %d)\n", path[j].x, path[j].y);
	} 
	else {
        printf("No solution exists.\n");
    }
}
	   
/*
 * Function: FindPath
 * Usage: if (FindPath(pt, path)) . . .
 * -------------------------------
 * This function attempts to generate a solution to the current
 * maze from point pt.  SolveMaze returns TRUE if the maze has
 * a solution and FALSE otherwise.  The implementation uses
 * recursion to solve the submazes that result from marking the
 * current square and moving one step along each open passage.
 * It sends the nodes included in the solution path and adds it
 * to an array.
 */

static bool FindPath(pointT pt, pointT *path){
    directionT dir;

	if (OutsideMaze(pt)){
		addSquareToArray(pt, path);
		return (TRUE);
	}
    if (IsMarked(pt))
		return (FALSE);
    MarkSquare(pt);
    for (dir = North; dir <= West; dir++) {
        if (!WallExists(pt, dir)) {
            if (FindPath(AdjacentPoint(pt, dir), path)) {
				addSquareToArray(pt, path);
                return (TRUE);
            }
        }
    }
    return (FALSE);
}

/*
 * Function: addSquareToArray
 * Usage: addSquareToArray(pt, path);
 * --------------------------------------
 * This function adds a pointT to an array;
 */

void addSquareToArray(pointT pt, pointT *path){
	int i=0;

	while(path[i].x >=0)
		i++;
	path[i] = pt;
}

/*
 * Function: AdjacentPoint
 * Usage: newpt = AdjacentPoint(pt, dir);
 * --------------------------------------
 * This function returns the pointT that results from moving
 * one square from pt in the direction specified by dir.  For
 * example, if pt is the point (1,1), AdjacentPoint(pt, East)
 * would return the point (2,1).
 */

static pointT AdjacentPoint(pointT pt, directionT dir)
{
    pointT newpt;

    newpt = pt;
    switch (dir) {
      case North: newpt.y++; break;
      case East:  newpt.x++; break;
      case South: newpt.y--; break;
      case West:  newpt.x--; break;;
    }
    return (newpt);
}

/*
 * Function: InitArray
 * Usage: InitArray(path);
 * --------------------------------------
 * This function fills the .x values in the array
 * with -1.
 */

void InitArray(pointT *path){
	int i;

	for(i = 0; i <= MaxPath; i++)
		path[i].x = -1;	
}
  